#!/usr/bin/python
# -*- coding: utf-8 -*-
'''
如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？ (表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解，比如1元换成2元的时候)
v[j]=1 3 5
d[i]=min(d[i-v[j]]+1),j=0,1,2,3···
'''

v=[1,3,5]
v.sort()
mubiao=11
li=[v[0]*x for x in range(mubiao+1)]

for i in range(1,mubiao+1):
    for j in range(len(v)):
        if i >= v[j] and li[i-v[j]]+1<li[i]:
            li[i]=li[i-v[j]]+1
print(li)
for i in range(1,mubiao+1):
    print("凑 %d 元最少需要 %d 枚硬币" %(i,li[i]))